import { Vec3, Node } from 'cc';

export interface Bounds {
    x: number;
    y: number;
    width: number;
    height: number;
}

/**
 * 四叉树节点
 * 
 * 功能：
 * 1. 空间分区管理
 * 2. 动态对象查询
 * 3. 区域碰撞检测
 * 4. 优化空间搜索
 */
export class QuadTreeNode {
    private bounds: Bounds;
    private maxObjects: number;
    private maxLevels: number;
    private level: number;
    private objects: Node[];
    private nodes: QuadTreeNode[];

    constructor(bounds: Bounds, maxObjects: number = 10, maxLevels: number = 5, level: number = 0) {
        this.bounds = bounds;
        this.maxObjects = maxObjects;
        this.maxLevels = maxLevels;
        this.level = level;
        this.objects = [];
        this.nodes = [];
    }

    public clear(): void {
        this.objects = [];
        for (const node of this.nodes) {
            node.clear();
        }
        this.nodes = [];
    }

    private split(): void {
        const subWidth = this.bounds.width / 2;
        const subHeight = this.bounds.height / 2;
        const x = this.bounds.x;
        const y = this.bounds.y;

        this.nodes[0] = new QuadTreeNode(
            { x: x + subWidth, y: y + subHeight, width: subWidth, height: subHeight },
            this.maxObjects,
            this.maxLevels,
            this.level + 1
        );

        this.nodes[1] = new QuadTreeNode(
            { x: x, y: y + subHeight, width: subWidth, height: subHeight },
            this.maxObjects,
            this.maxLevels,
            this.level + 1
        );

        this.nodes[2] = new QuadTreeNode(
            { x: x, y: y, width: subWidth, height: subHeight },
            this.maxObjects,
            this.maxLevels,
            this.level + 1
        );

        this.nodes[3] = new QuadTreeNode(
            { x: x + subWidth, y: y, width: subWidth, height: subHeight },
            this.maxObjects,
            this.maxLevels,
            this.level + 1
        );
    }

    private getIndex(bounds: Bounds): number {
        let index = -1;
        const verticalMidpoint = this.bounds.x + (this.bounds.width / 2);
        const horizontalMidpoint = this.bounds.y + (this.bounds.height / 2);

        const topQuadrant = (bounds.y + bounds.height > horizontalMidpoint);
        const bottomQuadrant = (bounds.y < horizontalMidpoint);

        if (bounds.x + bounds.width < verticalMidpoint) {
            if (topQuadrant) {
                index = 1;
            } else if (bottomQuadrant) {
                index = 2;
            }
        } else if (bounds.x > verticalMidpoint) {
            if (topQuadrant) {
                index = 0;
            } else if (bottomQuadrant) {
                index = 3;
            }
        }

        return index;
    }

    public insert(object: Node): void {
        if (this.nodes.length > 0) {
            const index = this.getIndex(this.getObjectBounds(object));
            if (index !== -1) {
                this.nodes[index].insert(object);
                return;
            }
        }

        this.objects.push(object);

        if (this.objects.length > this.maxObjects && this.level < this.maxLevels) {
            if (this.nodes.length === 0) {
                this.split();
            }

            let i = 0;
            while (i < this.objects.length) {
                const index = this.getIndex(this.getObjectBounds(this.objects[i]));
                if (index !== -1) {
                    this.nodes[index].insert(this.objects.splice(i, 1)[0]);
                } else {
                    i++;
                }
            }
        }
    }

    public retrieve(bounds: Bounds): Node[] {
        const index = this.getIndex(bounds);
        let returnObjects = this.objects;

        if (this.nodes.length > 0) {
            if (index !== -1) {
                returnObjects = returnObjects.concat(this.nodes[index].retrieve(bounds));
            } else {
                for (const node of this.nodes) {
                    returnObjects = returnObjects.concat(node.retrieve(bounds));
                }
            }
        }

        return returnObjects;
    }

    private getObjectBounds(object: Node): Bounds {
        return {
            x: object.position.x - 0.5,
            y: object.position.z - 0.5,
            width: 1,
            height: 1
        };
    }
} 